1. Field of the Invention
The present invention relates to a threshold secret sharing scheme for protecting secret information, a threshold secret sharing scheme, a secret information decryption method, and a program for carrying out the aforementioned threshold secret sharing scheme and secret information decryption method.
2. Description of the Related Art
In recent years, as information security becomes more and more important, there is an increased demand for countermeasures against information leaks and information loss. Accordingly, the (k,n) threshold secret sharing scheme as described in “How to share a secret” (A. Shamir, Commun. ACM, vol. 22 no. 11 pp. 612-613, 1979) (Non-patent document 1) has been attracting attention as a technique for maintaining information security while avoiding the risk of information loss. Here, in the (k,n) threshold secret sharing scheme, the confidential information is distributed into n shares (distribution). Furthermore, such an arrangement permits one to recover the information using desired k shares selected from among n shares (recovery).
However, in the (k,n) threshold secret sharing scheme described in “How to share a secret” (Non-patent document 1), decryption requires processing of a (k−1)-degree polynomial, leading to an enormous amount of calculation. In order to solve this problem, a (2,n) threshold secret sharing scheme using exclusive-OR (XOR) operations has been proposed as described in “A Fast (2, n)-Threshold Scheme and Its Application” (Yoshihiro Fujii, Minako Tada, Norikazu Hosaka, Koya Tochikubo, Takehisa Kato, proceeding of CSS2005, 2005) (Non-patent document 2), which provides high-speed distribution and recovery.
Also, as a threshold secret sharing scheme using XOR operations with a number of thresholds other than 2, “A (3,n)-threshold secret sharing scheme using XOR operations” (Jun Kurihara, Shinsaku Kiyomoto, Kazuhide Fukushima, Toshiaki Tanaka, proceeding of SCIS2007, 2007) (Non-patent document 3) proposes a (3,n) threshold secret sharing scheme using exclusive-OR (XOR) operations. However, no threshold secret sharing scheme using XOR operations has been proposed in which the number of thresholds is 4 or more. “How to convert 1-out-of-n proof into k-out-of-n proof” (Nobuyuki Shiina, Takeshi Okamoto, Eiji Okamoto, proceeding of SCIS2004, 2004) (Non-patent document 4) also proposes a (k,n) threshold secret sharing scheme using XOR operations or additive operations, which provides high-speed distribution and recovery. However, such a scheme requires a share data length which is several times greater than the data length of the secret information, leading to poor efficiency. Also, Japanese Unexamined Patent Application publication No. 2006-18850 (Patent document 1) proposes a (k,n) threshold secret sharing scheme. However, in some cases, such a scheme permits one to decrypt the secret information with the number of available shares being smaller than k, which does not satisfy the integrity of the threshold secret sharing scheme.